package main

//判断一个 9x9 的数独是否有效。只需要根据以下规则，验证已经填入的数字是否有效即可。
//
//
// 数字 1-9 在每一行只能出现一次。
// 数字 1-9 在每一列只能出现一次。
// 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
//
//
//
//
// 上图是一个部分填充的有效的数独。
//
// 数独部分空格内已填入了数字，空白格用 '.' 表示。
//
// 示例 1:
//
// 输入:
//[
//  ["5","3",".",".","7",".",".",".","."],
//  ["6",".",".","1","9","5",".",".","."],
//  [".","9","8",".",".",".",".","6","."],
//  ["8",".",".",".","6",".",".",".","3"],
//  ["4",".",".","8",".","3",".",".","1"],
//  ["7",".",".",".","2",".",".",".","6"],
//  [".","6",".",".",".",".","2","8","."],
//  [".",".",".","4","1","9",".",".","5"],
//  [".",".",".",".","8",".",".","7","9"]
//]
//输出: true
//
//
// 示例 2:
//
// 输入:
//[
//  ["8","3",".",".","7",".",".",".","."],
//  ["6",".",".","1","9","5",".",".","."],
//  [".","9","8",".",".",".",".","6","."],
//  ["8",".",".",".","6",".",".",".","3"],
//  ["4",".",".","8",".","3",".",".","1"],
//  ["7",".",".",".","2",".",".",".","6"],
//  [".","6",".",".",".",".","2","8","."],
//  [".",".",".","4","1","9",".",".","5"],
//  [".",".",".",".","8",".",".","7","9"]
//]
//输出: false
//解释: 除了第一行的第一个数字从 5 改为 8 以外，空格内其他数字均与 示例1 相同。
//     但由于位于左上角的 3x3 宫内有两个 8 存在, 因此这个数独是无效的。
//
// 说明:
//
//
// 一个有效的数独（部分已被填充）不一定是可解的。
// 只需要根据以上规则，验证已经填入的数字是否有效即可。
// 给定数独序列只包含数字 1-9 和字符 '.' 。
// 给定数独永远是 9x9 形式的。
//
// Related Topics 哈希表

/*
	思路1:暴力解法
	给定哈希表、存储每个数字的攻击范围
	直接遍历数独矩阵、逐个判断
	时间复杂度:O(n^2)
	难点:3*3的范围判断:
		对于坐标(i,j)的范围计算如下:f(i,j)=i/3*3+j/3
		会依次得到0,1,2,3,4,5,6,7,8几个子范围
*/
type Set struct {
	Row      map[byte]map[int]bool
	Col      map[byte]map[int]bool
	BoxIndex map[byte]map[int]bool
}

//leetcode submit region begin(Prohibit modification and deletion)
func isValidSudoku(board [][]byte) bool {
	set := Set{}
	// 初始化集合
	for i := 0; i < len(board); i++ {
		set.Row = make(map[byte]map[int]bool)
		set.Col = make(map[byte]map[int]bool)
		set.BoxIndex = make(map[byte]map[int]bool)
		for j := 0; j < 9; j++{
			set.Row[byte(j)] = make(map[int]bool)
			set.Col[byte(j)] = make(map[int]bool)
			set.BoxIndex[byte(j)] = make(map[int]bool)
		}
	}
	for i := 0; i < len(board); i++ {
		for j := 0; j < len(board[i]); j++ {
			if board[i][j] == '.' {
				continue
			}
			data := board[i][j] - 49 // 注意、因为是下标index、所以这里要减49、得到的范围为0~8
			if data != 254 && (set.Row[data][i] || set.Col[data][j] || set.BoxIndex[data][i/3*3+j/3]) {
				return false
			}
			set.Row[data][i] = true
			set.Col[data][j] = true
			set.BoxIndex[data][i/3*3+j/3] = true
		}
	}
	return true
}

//leetcode submit region end(Prohibit modification and deletion)
